package string;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @Description 剑指 Offer 50. 第一个只出现一次的字符
 * @Author Firenut
 * @Date 2023-01-21 15:45
 */
public class T50_firstUniqChar {
    // 法4 使用LinkedHashMap
    public char firstUniqChar5(String s) {
        Map<Character,Boolean> map=new LinkedHashMap<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            map.put(ch, !map.containsKey(ch));
        }

        // 使用LinkedHashMap,会维护插入的先后顺序，而字符串的长度可能很长，如果使用HashMap,在进行第二次遍历的时候就需要遍历整个字符串，而使用LinkedHashMap之后，长度最大也就是26,所以查询效率比较高
        for(Map.Entry<Character,Boolean>m : map.entrySet()){
            if(m.getValue()){
                return m.getKey();
            }
        }
        return ' ';
    }


    // 法3 使用数组
    public char firstUniqChar4(String s) {
        int []map=new int[26];
        for(int i=0;i<s.length();i++){
            map[s.charAt(i)-'a']++;
        }
        for(int i=0;i<s.length();i++){
            if(map[s.charAt(i)-'a']==1){
                return s.charAt(i);
            }
        }
        return ' ';
    }

    // 法2 优化
    public char firstUniqChar3(String s) {
        Map<Character,Boolean> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            map.put(ch, !map.containsKey(ch));
        }

        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(map.containsKey(ch)&&map.get(ch)){
                return ch;
            }
        }
        return ' ';
    }


    // 法2: 使用HashMap,第一轮循环是记录映射关系,
    // 第二轮循环是遍历字符串找满足条件的第一个字符
    public char firstUniqChar2(String s) {
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(!map.containsKey(ch)){
                map.put(ch,1);
            }else{ //其实这一段可以用 true,false,不用关心记录了多少次
                Integer val=map.get(ch);
                val+=1;
                map.put(ch,val);
            }
        }

        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(map.containsKey(ch)){
                if(map.get(ch)==1){
                    return ch;
                }
            }
        }
        return ' ';
    }

    // 法1: LinkedHashMap
    public char firstUniqChar(String s) {
        Map<Character,Integer> map=new LinkedHashMap<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(!map.containsKey(ch)){
                map.put(ch,1);
            }else{
                Integer val=map.get(ch);
                val+=1;
                map.put(ch,val);
            }
        }
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            if(entry.getValue()==1){
                return entry.getKey();
            }
        }

        return ' ';
    }


    // 法1: 优化
    public char firstUniqChar1(String s) {
        Map<Character,Boolean> map=new LinkedHashMap<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            map.put(ch, !map.containsKey(ch)); //首次添加为true,表示只有一个;为false表示多次
        }
        for(Map.Entry<Character,Boolean> entry:map.entrySet()){
            if (entry.getValue()) {
                return entry.getKey();
            }
        }
        return ' ';
    }
}
